package DP;

/**
 * @Author: Gosin
 * @Date: 2020/5/27 15:02
 */
public class NumDecodings {
    public static void main(String[] args) {
        String s ="01";
        NumDecodings decodings = new NumDecodings();
        int i = decodings.numDecodings(s);
        System.out.println(i);

    }
    public int numDecodings(String s) {
        int len = s.length();
        if(len==0){
            return 0;
        }
        if(len==1){
            return Integer.parseInt(s.substring(0,1))>0?1:0;
        }
        int[] dp = new int[len];
        dp[0] = Integer.parseInt(s.substring(0,1))>0?1:0;
        dp[1] = (Integer.parseInt(s.substring(1,2))>0?dp[0]:0) ;
        if(Integer.parseInt(s.substring(0,2))<= 26 && Integer.parseInt(s.substring(0,2))>=10){
            dp[1] +=1;
        }
        for(int i=2;i<len;i++){
            boolean b1 = Integer.parseInt(s.substring(i, i + 1)) > 0;
            boolean b2 = false;
            if(Integer.parseInt(s.substring(i - 1, i + 1)) <= 26 && Integer.parseInt(s.substring(i - 1, i + 1)) >= 10){
                 b2 =true ;
            }
            dp[i] = (b1?dp[i-1]:0) + (b2?dp[i-2]:0);
        }
        return dp[len-1];
    }
}
